package org.jiang.springbootdemo.demos.web.test.programmingTest;

/*
    字符串（从i开始遍历） 从后往前查找重复的字符，能形成回文子串的必然是最大的
 */
public class LongestPalindrome {

    public static String longestPalindrome(String s) {
        int len;
        if (s == null || (len = s.length()) == 0) return "";
        if (len == 1) return s;
        String result = s.substring(0,1);
        String resTmp = "";
        int maxTmp = 0;
        int max = 1, tmp = 0;
        char ch;
        boolean flag = true;
        for (int i = 0; i < len; i++) {
            ch = s.charAt(i);
            tmp = 0;
            // 最后一个无法形成回文子串
            if (i != len - 1) flag = true;
            while (flag) {
                // 查找char[i]对应的字符的下标tmp
                if (tmp == 0) tmp = s.lastIndexOf(ch);
                else tmp = s.lastIndexOf(ch, tmp - 1);
                if (tmp < i || tmp == i) {
                    flag = false;
                    continue;
                }
                // 判断是否是双向队列
                resTmp = s.substring(i, tmp + 1);
                maxTmp = tmp - i + 1;
                if (valid(resTmp)) {
                    if (maxTmp > max) {
                        result = resTmp;
                        max = maxTmp;
                    }
                    flag = false;
                }
            }
        }
        return result;
    }

    public static boolean valid (String str) {
        int start = 0;
        int end = str.length() - 1;
        while (true) {
            if (str.charAt(start++) != str.charAt(end--)) return false;
            if (end <= start) return true;
        }
    }

    public static void main(String[] args) {
        System.out.println("最长的回文串：" + longestPalindrome("bbab"));
        System.out.println("最长的回文串：" + longestPalindrome("bbabb"));
        System.out.println("最长的回文串：" + longestPalindrome("bb"));
        System.out.println("最长的回文串：" + longestPalindrome("a"));
        System.out.println("最长的回文串：" + longestPalindrome("ac"));
        System.out.println("最长的回文串：" + longestPalindrome("aacabdkacaa"));
        System.out.println("最长的回文串：" + longestPalindrome("cbbd"));
        System.out.println("最长的回文串：" + longestPalindrome("eabcb"));
        System.out.println("最长的回文串：" + longestPalindrome("aacabdkacaa"));
    }
}
